package zero.slr;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

import org.apache.poi.hssf.usermodel.HSSFCell;
import org.apache.poi.hssf.usermodel.HSSFRow;
import org.apache.poi.hssf.usermodel.HSSFSheet;
import org.apache.poi.hssf.usermodel.HSSFWorkbook;

import java.util.Map.Entry;

import zero.entity.Production;
import zero.lex.Token;

/**
 * 语法分析
 *
 * @author Zero
 *
 */
public class Parser {
    private static Parser                 parser;
    private static final String           PRODUCTION_FILE = "production2.txt";
    private List<Production>              productions;
    private List<Production>              expandProductions;
    private ItemSetFamily                 itemSetFamily;
    private Map<String, Set<String>>      firstMap;
    private Map<String, Set<String>>      followMap;
    private Set<String>                   variableSet;                        // 语法变量集
    private Set<String>                   terminatorSet;                      // 终结符集
    private List<Map<String, ActionUnit>> actionTbl;                          // action表
    private List<Map<String, GotoUnit>>   gotoTbl;                            // goto表

    private Parser() {
        productions   = new ArrayList<>();
        variableSet   = new HashSet<>();
        terminatorSet = new HashSet<>();
    }

    public static Parser getInstance() {
        if (parser == null) {
            parser = new Parser();
        }

        return parser;
    }

    public void init() throws IOException {
        initProductions();
        initExpandProductions();
        initFirstMap();
        initFollowMap();

        // outputProductions();
        outputFirst();
        outputFollow();

        itemSetFamily = new ItemSetFamily(expandProductions);
        itemSetFamily.init();
        // System.out.println(itemSetFamily.toString());

        initActionGoto();
        outputAction();
        outputGoto();
    }

    private void initProductions() {
        try (BufferedReader br = new BufferedReader(new FileReader(PRODUCTION_FILE))) {
            String       line;
            String       left   = null;
            List<String> right  = null;
            int          number = 1;

            while ((line = br.readLine()) != null) {
                line = line.trim();
                if (line.equals("")) {
                    continue;
                }

                if (line.charAt(0) == '/' && line.charAt(1) == '/') {
                    continue;
                }

                String[] strs = line.split("@");

                // 保存产生式左部
                left  = strs[0].trim();
                // 保存产生式右部
                right = Arrays.asList(strs[1].trim().split("\\s+"));

                // 语法变量都在左部式
                variableSet.add(left);

                // 先把所有的符号都引入进来，循环结束后再除去语法变量
                terminatorSet.addAll(right);

                Production production = new Production(number++, left, right);
                productions.add(production);
            }

            terminatorSet.removeAll(variableSet);

        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private void initExpandProductions() {
        expandProductions = new ArrayList<>();

        Production   production = new Production();
        List<String> right      = new ArrayList<>();

        right.add(productions.get(0).getLeft());
        production.setLeft("开始");
        production.setRight(right);
        production.setNumber(0);

        expandProductions.add(production);
        expandProductions.addAll(productions);
    }

    private void initFirstMap() {
        firstMap = new HashMap<>();

        // 终结符的 first
        for (String terminator : terminatorSet) {
            Set<String> first = new HashSet<>();
            first.add(terminator);
            firstMap.put(terminator, first);
        }

        for (Production p : expandProductions) {
            String      v     = p.getLeft();
            Set<String> first = new HashSet<>();

            if (firstMap.containsKey(v)) {
                continue;
            }

            // 把形如 X -> a... 这类的a拉入first集
            for (Production p1 : expandProductions) {
                if (p1.getLeft().equals(v)) {
                    String firstElement = p1.getRight().get(0);

                    if (isTerminator(firstElement) || firstElement.equals("$")) {
                        first.add(firstElement);
                    }
                }
            }

            firstMap.put(v, first);
        }

        boolean isChanged;

        do {
            isChanged = false; // 如果没有元素first发生了变化则为false，如果有变化则为true

            for (Production p : productions) {
                String      v     = p.getLeft();
                Set<String> first = new HashSet<>();

                for (int i = 0; i < p.getRight().size(); ++i) {

                    String  rightEle   = p.getRight().get(i);

                    boolean hasEpsilon = false;

                    // 便利右部第i个元素的first集
                    for (String x : firstMap.get(rightEle)) {
                        if (x.equals("$")) {
                            hasEpsilon = true;
                            continue;
                        }

                        first.add(x);
                    }

                    if (i == p.getRight().size() - 1 && hasEpsilon) {
                        first.add("$");
                    }

                    if (!hasEpsilon) {
                        break;
                    }
                }

                int orginSize = firstMap.get(v).size();

                firstMap.get(v).addAll(first);

                if (firstMap.get(v).size() > orginSize) {
                    isChanged = true;
                }
            }

        } while (isChanged);

    }

    private void initFollowMap() {
        followMap = new HashMap<>();

        for (String v : variableSet) {
            HashSet<String> follow = new HashSet<>();
            followMap.put(v, follow);
        }

        // 初始化开始符号FOLLOW{S}为#
        followMap.get(productions.get(0).getLeft()).add("#");

        boolean isChanged = false;

        do {
            isChanged = false;

            for (String v : variableSet) {
                for (Production p : productions) {
                    if (!p.getLeft().equals(v)) {
                        continue;
                    }

                    for (int i = 0; i < p.getRight().size(); ++i) {
                        String rightEle = p.getRight().get(i);

                        if (isTerminator(rightEle)) {
                            continue;
                        }

                        // 求rightEle的follow
                        Set<String> follow = new HashSet<>();

                        if (i == p.getRight().size() - 1) {
                            follow.addAll(followMap.get(v));
                        }

                        for (int j = i + 1; j < p.getRight().size(); ++j) {
                            String nextEle = p.getRight().get(j);

                            if (!firstMap.get(nextEle).contains("$")) {
                                follow.addAll(firstMap.get(nextEle));
                                break;
                            }

                            for (String s : firstMap.get(nextEle)) {
                                if (s.equals("$")) {
                                    continue;
                                }
                                follow.add(s);
                            }

                            if (j == p.getRight().size() - 1) {
                                follow.addAll(followMap.get(v));
                            }
                        }

                        int orginSize = followMap.get(rightEle).size();

                        followMap.get(rightEle).addAll(follow);

                        if (followMap.get(rightEle).size() > orginSize) {
                            isChanged = true;
                        }
                    }
                }
            }
        } while (isChanged);
    }

    private void createActionTbl() {
        actionTbl = new ArrayList<>();

        for (int i = 0; i < itemSetFamily.getItemSets().size(); ++i) {
            HashMap<String, ActionUnit> map = new HashMap<>();

            for (String terminator : terminatorSet) {
                map.put(terminator, null);
            }
            map.put("#", null);
            actionTbl.add(map);
        }
    }

    private void createGotoTbl() {
        gotoTbl = new ArrayList<>();

        for (int i = 0; i < itemSetFamily.getItemSets().size(); ++i) {
            HashMap<String, GotoUnit> map = new HashMap<>();

            for (String variable : variableSet) {
                map.put(variable, null);
            }

            gotoTbl.add(map);
        }
    }

    public void initActionGoto() {
        createActionTbl();
        createGotoTbl();

        List<ItemSet> itemSets = itemSetFamily.getItemSets();

        for (int i = 0; i < itemSets.size(); ++i) {
            ItemSet is = itemSets.get(i);

            for (Item item : is.getItems()) {
                List<String> right      = item.getRight();
                Production   production = item.getProduction();
                int          pos        = item.getPos();

                // 当小圆点在最后一个位置的时候
                if (pos == right.size()) {
                    // 最初那个产生式
                    if (production.equals(expandProductions.get(0))) {
                        insertAction(i, "#", new ActionUnit(ActionUnit.ACC, null));
                        continue;
                    }

                    // 获取左部的follow集
                    Set<String> follow = followMap.get(item.getLeft());
                    int         j      = item.getProduction().getNumber();

                    for (String a : follow) {
                        insertAction(i, a, new ActionUnit(ActionUnit.REDUCE, j));
                    }

                    continue;
                }

                String  trigger   = right.get(pos);
                ItemSet goItemSet = is.getGoMap().get(trigger);
                int     j         = goItemSet.getNumber();

                // 需要看后面的是终结符还是语法变量
                if (isTerminator(trigger)) {
                    insertAction(i, trigger, new ActionUnit(ActionUnit.STEP, j));
                } else {
                    insertGoto(i, trigger, new GotoUnit(j));
                }
            }
        }
    }

    public void insertAction(int key1, String key2, ActionUnit value) {
        actionTbl.get(key1).put(key2, value);
    }

    public void insertGoto(int key1, String key2, GotoUnit value) {
        gotoTbl.get(key1).put(key2, value);
    }

    public ActionUnit getAction(int key1, String key2) {
        return actionTbl.get(key1).get(key2);
    }

    public GotoUnit getGoto(int key1, String key2) {
        return gotoTbl.get(key1).get(key2);
    }

    /**
     * 判断输入是否为终结符
     */
    public boolean isTerminator(String input) {
        if (terminatorSet.contains(input)) {
            return true;
        }

        if (variableSet.contains(input)) {
            return false;
        }

        return false;
    }

    public void analyze(List<Token> tokenList) {
        Stack<Integer> statusStack = new Stack<>();
        Stack<String>  symbolStack = new Stack<>();
        boolean        success     = false;

        statusStack.push(0);
        int ip = 0;

        System.out.println("========== Begin stack ==========");

        Token sentry = new Token();

        sentry.setContent("#");
        tokenList.add(sentry);

        do {
            Token   token     = tokenList.get(ip);
            String  symbol    = token.getContent();
            Integer topStatus = statusStack.peek();

            if (!isTerminator(symbol) && !symbol.equals("#")) {
                int id = token.getId();

                if (id == 1) {
                    symbol = "标识符";
                } else if (id == 2) {
                    symbol = "常数";
                } else {
                    error("[" + token.toString() + "]: " + symbol + " is invalid!");
                    return;
                }
            }

            ActionUnit action = getAction(topStatus, symbol);

            if (action == null) {
                error(token);
                return;
            }

            switch (action.getAction()) {
            case ActionUnit.STEP:
                symbolStack.push(symbol);
                statusStack.push(action.getDest());
                printStack(symbolStack, statusStack);
                ++ip;
                break;
            case ActionUnit.REDUCE:
                Production p = expandProductions.get(action.getDest());

                for (int i = 0; i < p.getRight().size(); ++i) {
                    symbolStack.pop();
                    statusStack.pop();
                }

                topStatus = statusStack.peek();

                symbolStack.push(p.getLeft());
                statusStack.push(gotoTbl.get(topStatus).get(p.getLeft()).getDest());

                printStack(symbolStack, statusStack);
                System.out.println("Reduced by: " + p.toString());
                break;
            case ActionUnit.ACC:
                success = true;
                break;
            default:
                error();
                return;
            }
        } while (!success);

        System.out.println("Acc!");
    }

    public void error() {
        System.err.println("Not acc.");
    }

    public void error(Token token) {
        System.err.printf("Syntax error! '%s' Position: line %d column %d\n", token.getContent(), token.getLineNo(),
                token.getColumnNo());
    }

    public void error(String msg) {
        System.err.println(msg);
    }

    public void outputProductions() {
        for (Production p : expandProductions) {
            System.out.println(p.toString());
        }
    }

    public void outputFirst() {
        System.out.println("\n========== FIRST ==========");
        for (Entry<String, Set<String>> entry : this.firstMap.entrySet()) {
            System.out.println("********** " + entry.getKey() + " **********");
            for (String s : entry.getValue()) {
                System.out.print(s + " ");
            }
            System.out.println();
        }
    }

    public void outputFollow() {
        System.out.println("\n========== FOLLOW ==========");
        for (Entry<String, Set<String>> entry : followMap.entrySet()) {
            System.out.println("********** " + entry.getKey() + " **********");

            for (String s : entry.getValue()) {
                System.out.print(s + " ");
            }
            System.out.println();
        }
    }

    public void outputAction() throws IOException {
        HSSFWorkbook hssfWorkbook = new HSSFWorkbook();
        HSSFSheet    hssfSheet    = hssfWorkbook.createSheet("action");

        HSSFRow      row;
        HSSFCell     cell;
        int          i            = 0;

        for (Map<String, ActionUnit> map : actionTbl) {
            row = hssfSheet.createRow(i++);

            int j = 0;
            cell = row.createCell(j++);
            cell.setCellValue("状态");

            for (Entry<String, ActionUnit> entry : map.entrySet()) {
                cell = row.createCell(j++);
                cell.setCellValue(entry.getKey());
            }
            break;
        }

        int k = 0;
        for (Map<String, ActionUnit> map : actionTbl) {
            row = hssfSheet.createRow(i++);

            int j = 0;
            cell = row.createCell(j++);
            cell.setCellValue(k++);

            for (Entry<String, ActionUnit> entry : map.entrySet()) {
                cell = row.createCell(j++);

                ActionUnit a = entry.getValue();

                if (a == null) {
                    cell.setCellValue("");
                } else {

                    if (a.getAction() == ActionUnit.STEP) {
                        cell.setCellValue("S" + a.getDest());
                    } else if (a.getAction() == ActionUnit.REDUCE) {
                        cell.setCellValue("r" + a.getDest());
                    } else {
                        cell.setCellValue("ACC");
                    }
                }
            }
        }

        FileOutputStream out = new FileOutputStream("C:\\Users\\Zero Sharp\\Desktop\\actionTable.xls");
        hssfWorkbook.write(out);
        out.flush();

        hssfWorkbook.close();
    }

    public void outputGoto() throws IOException {
        HSSFWorkbook hssfWorkbook = new HSSFWorkbook();
        HSSFSheet    hssfSheet    = hssfWorkbook.createSheet("goto");

        HSSFRow      row;
        HSSFCell     cell;
        int          i            = 0;

        for (Map<String, GotoUnit> map : this.gotoTbl) {
            row = hssfSheet.createRow(i++);
            int j = 0;
            cell = row.createCell(j++);
            cell.setCellValue("状态");
            for (Entry<String, GotoUnit> entry : map.entrySet()) {
                cell = row.createCell(j++);
                cell.setCellValue(entry.getKey());
            }
            break;
        }

        int k = 0;
        for (Map<String, GotoUnit> map : gotoTbl) {
            row = hssfSheet.createRow(i++);

            int j = 0;
            cell = row.createCell(j++);
            cell.setCellValue(k++);

            for (Entry<String, GotoUnit> entry : map.entrySet()) {
                cell = row.createCell(j++);

                GotoUnit a = entry.getValue();

                if (a == null) {
                    cell.setCellValue("");
                } else {
                    cell.setCellValue(a.getDest());
                }
            }
        }

        FileOutputStream out = new FileOutputStream("C:\\Users\\Zero Sharp\\Desktop\\gotoTable.xls");
        hssfWorkbook.write(out);
        out.flush();

        hssfWorkbook.close();
    }

    private void printStack(Stack<String> s1, Stack<Integer> s2) {
        Iterator<String> it1 = s1.iterator();
        while (it1.hasNext()) {
            System.out.print(it1.next() + " ");
        }
        System.out.print("\t#\t");

        Iterator<Integer> it2 = s2.iterator();
        while (it2.hasNext()) {
            System.out.print(" " + it2.next());
        }

        System.out.println();
    }
}
